package com.db.collections;

public class IntHashMap extends AbstractIntMap implements IntMap {

  /**
   * The default initial capacity - MUST be a power of two.
   */
  static final int DEFAULT_INITIAL_CAPACITY = 16;

  /**
   * The maximum capacity, used if a higher value is implicitly specified by
   * either of the constructors with arguments. MUST be a power of two <= 1<<30.
   */
  static final int MAXIMUM_CAPACITY = 1 << 30;

  /**
   * The load factor used when none specified in constructor.
   */
  static final float DEFAULT_LOAD_FACTOR = 0.75f;

  /**
   * The table, resized as necessary. Length MUST Always be a power of two.
   */
  transient IntEntry[] table;

  /**
   * The number of key-value mappings contained in this map.
   */
  transient int size;

  /**
   * The next size value at which to resize (capacity * load factor).
   * 
   * @serial
   */
  int threshold;

  /**
   * The load factor for the hash table.
   * 
   * @serial
   */
  final float loadFactor;

  /**
   * The number of times this HashMap has been structurally modified Structural
   * modifications are those that change the number of mappings in the HashMap
   * or otherwise modify its internal structure (e.g., rehash). This field is
   * used to make iterators on Collection-views of the HashMap fail-fast. (See
   * ConcurrentModificationException).
   */
  transient int modCount;

  /**
   * Constructs an empty <tt>IntHashMap</tt> with the specified initial capacity
   * and load factor.
   * 
   * @param initialCapacity
   *          the initial capacity
   * @param loadFactor
   *          the load factor
   * @throws IllegalArgumentException
   *           if the initial capacity is negative or the load factor is
   *           nonpositive
   */
  public IntHashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
      throw new IllegalArgumentException("Illegal initial capacity: "
          + initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
      initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
      throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

    // Find a power of 2 >= initialCapacity
    int capacity = 1;
    while (capacity < initialCapacity)
      capacity <<= 1;

    this.loadFactor = loadFactor;
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new IntEntry[capacity];
    init();
  }

  void init() {
  }

  /**
   * Constructs an empty <tt>IntHashMap</tt> with the specified initial capacity
   * and the default load factor (0.75).
   * 
   * @param initialCapacity
   *          the initial capacity.
   * @throws IllegalArgumentException
   *           if the initial capacity is negative.
   */
  public IntHashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
  }

  /**
   * Constructs an empty <tt>HashMap</tt> with the default initial capacity (16)
   * and the default load factor (0.75).
   */
  public IntHashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
  }

  /**
   * Returns index for hash code h.
   */
  static int indexFor(int h, int length) {
    return h & (length - 1);
  }

  /**
   * Returns the number of key-value mappings in this map.
   * 
   * @return the number of key-value mappings in this map
   */
  @Override
  public int size() {
    return size;
  }

  /**
   * Returns <tt>true</tt> if this map contains no key-value mappings.
   * 
   * @return <tt>true</tt> if this map contains no key-value mappings
   */
  @Override
  public boolean isEmpty() {
    return size == 0;
  }

  @Override
  public boolean put(int key, int value) {
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (IntEntry e = table[i]; e != null; e = e.next) {
      if (e.hash == hash && (e.key == key)) {
        e.value = value;
        e.recordAccess(this);
        return true;
      }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return false;

  }

  @Override
  public Integer get(int key) {
    IntEntry entry = getEntry(key);
    return null == entry ? null : entry.getValue();
  }

  @Override
  public boolean remove(int key) {
    IntEntry e = removeEntryForKey(key);
    return (e == null ? false : true);
  }

  /**
   * Removes all of the mappings from this map. The map will be empty after this
   * call returns.
   */
  @Override
  public void clear() {
    modCount++;
    IntEntry[] tab = table;
    for (int i = 0; i < tab.length; i++)
      tab[i] = null;
    size = 0;
  }

  @Override
  public boolean contains(int key) {
    return getEntry(key) != null;
  }

  final IntEntry getEntry(int key) {
    int hash = hash(key);
    for (IntEntry e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
      if (e.hash == hash && (e.key == key))
        return e;
    }
    return null;
  }

  final int hash(int k) {
    int h = 0;

    h ^= k;

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
  }

  static class IntEntry implements IntMap.IntEntry {
    final int key;
    int value;
    IntEntry next;
    int hash;

    /**
     * Creates new entry.
     */
    IntEntry(int h, int k, int v, IntEntry n) {
      value = v;
      next = n;
      key = k;
      hash = h;
    }

    public final int getKey() {
      return key;
    }

    public final int getValue() {
      return value;
    }

    public final int setValue(int newValue) {
      int oldValue = value;
      value = newValue;
      return oldValue;
    }

    public final boolean equals(Object o) {
      if (!(o instanceof IntMap.IntEntry))
        return false;
      IntMap.IntEntry e = (IntMap.IntEntry) o;
      int k1 = getKey();
      int k2 = e.getKey();
      if (k1 == k2) {
        int v1 = getValue();
        int v2 = e.getValue();
        if (v1 == v2)
          return true;
      }
      return false;
    }

    public final int hashCode() {
      return (key ^ value);
    }

    public final String toString() {
      return getKey() + "=" + getValue();
    }

    void recordAccess(IntHashMap m) {
    }

    void recordRemoval(IntHashMap m) {
    }

  }

  final IntEntry removeEntryForKey(int key) {
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    IntEntry prev = table[i];
    IntEntry e = prev;

    while (e != null) {
      IntEntry next = e.next;
      if (e.hash == hash && (e.key == key)) {
        modCount++;
        size--;
        if (prev == e)
          table[i] = next;
        else
          prev.next = next;
        e.recordRemoval(this);
        return e;
      }
      prev = e;
      e = next;
    }

    return e;
  }

  void addEntry(int hash, int key, int value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
      resize(2 * table.length);
      hash = hash(key);
      bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
  }

  void createEntry(int hash, int key, int value, int bucketIndex) {
    IntEntry e = table[bucketIndex];
    table[bucketIndex] = new IntEntry(hash, key, value, e);
    size++;
  }

  void resize(int newCapacity) {
    IntEntry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
      threshold = Integer.MAX_VALUE;
      return;
    }

    IntEntry[] newTable = new IntEntry[newCapacity];
    boolean rehash = true;
    transfer(newTable, rehash);
    table = newTable;
    threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
  }

  void transfer(IntEntry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (IntEntry e : table) {
      while (null != e) {
        IntEntry next = e.next;
        if (rehash) {
          e.hash = hash(e.key);
        }
        int i = indexFor(e.hash, newCapacity);
        e.next = newTable[i];
        newTable[i] = e;
        e = next;
      }
    }
  }
}
